public class addInList {
    /**
     * 链表相加
     * 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
        给定两个这种链表，请生成代表两个整数相加值的结果链表。
        
     * @param head1
     * @param head2
     * @return
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        ListNode r1 = reverse(head1);
        ListNode r2 = reverse(head2);

        int jin = 0;
        ListNode ret_pre = new ListNode(-1);
        ListNode cur = ret_pre;
        while (r1 != null || r2 != null) {
            int sum = 0;
            if (r1 != null && r2 != null) {
                sum = r1.val + r2.val + jin;
                r1 = r1.next;
                r2 = r2.next;
            } else if (r1 != null) {
                sum = r1.val + jin;
                r1 = r1.next;
            } else {
                sum = r2.val + jin;
                r2 = r2.next;
            }
            jin = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
        }
        if (jin > 0) {
            cur.next = new ListNode(jin);
        }
        return reverse(ret_pre.next);
    }

    private ListNode reverse(ListNode head) {
        ListNode cur = head, pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
